/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package net.ieslaferreria.lib.tipusdinamics;

/**
 *
 * @author Administrador
 */
public class CuaPrioritariaVectorImpl{
    ArbreBinariQuasicomplertVectorImpl pilo;
    Comparator comparator = null;
    int ascendent = 1;

    public CuaPrioritariaVectorImpl() {
        pilo = new ArbreBinariQuasicomplertVectorImpl();
    }
    
    public CuaPrioritariaVectorImpl(int mida) {
        pilo = new ArbreBinariQuasicomplertVectorImpl(mida);
    }
    
    public void setComparator(Comparator comp){
        comparator = comp;
    }
    
    public boolean esBuida() {
        return pilo.esBuit();
    }

    public Object getDada() {
        return pilo.getDada(pilo.getArrel());
    }

    public void encua(Object c) {
        int pos = this.pilo.afegirDarrer(c);
        pujaDada(pos);
    }

    public Object escapca() {
        Object aux = this.getDada();
        intercanviaDades(this.pilo.getArrel(), this.pilo.darrer());   
        this.pilo.esborrarDarrer();
        enfonsaDada(this.pilo.getArrel());
        return aux;
    }
    
    public int size(){
        return pilo.size;
    }
    
    public void setOrdreInvers(){
        this.ascendent *= -1;
    }
    
    protected void intercanviaDades(int pos1, int pos2){
        Object aux = this.pilo.elems[pos1];
        this.pilo.elems[pos1]= this.pilo.elems[pos2];
        this.pilo.elems[pos2]=aux;
    }

    protected void pujaDada(int pos){
	if((this.pilo.tePare(pos)) 
                    && (this.esMenorQue(this.pilo.getDada(pos), 
                                        this.pilo.getDada(this.pilo.getPare(pos))))){
		this.intercanviaDades(pos, this.pilo.getPare(pos));
                pujaDada(this.pilo.getPare(pos));
	}
    }

    protected void enfonsaDada(int pos){
	if((pilo.teFillEsq(pos)) 
                    && (!this.esMenorQue(this.pilo.getDada(pos),
                                         this.pilo.getDada(this.pilo.getFillEsq(pos))))
                    || (this.pilo.teFillDret(pos))
                    && (!this.esMenorQue(this.pilo.getDada(pos),
                                         this.pilo.getDada(this.pilo.getFillDret(pos))))){

                if(!this.pilo.teFillEsq(pos)){
			this.intercanviaDades(pos, this.pilo.getFillDret(pos));
                        enfonsaDada(this.pilo.getFillDret(pos));
		}else if(!this.pilo.teFillDret(pos)){
			this.intercanviaDades(pos, this.pilo.getFillEsq(pos));
                        enfonsaDada(this.pilo.getFillEsq(pos));
		}else if(this.esMenorQue(this.pilo.getDada(this.pilo.getFillEsq(pos)), 
                                            this.pilo.getDada(this.pilo.getFillDret(pos)))){
			this.intercanviaDades(pos, this.pilo.getFillEsq(pos));
                        enfonsaDada(this.pilo.getFillEsq(pos));
		}else{
			this.intercanviaDades(pos, this.pilo.getFillDret(pos));
                        enfonsaDada(this.pilo.getFillDret(pos));
		}
	}
    }
    
    protected boolean esMenorQue(Object c1, Object c2){
        boolean ret;
        if(comparator==null){
            ret =((this.ascendent*((Comparable)c1).compareTo(c2))<0);
        }else{
            ret = ((this.ascendent*comparator.compare(c1, c2))<0);
        }
        return ret;
    }
    

    protected static class ArbreBinariQuasicomplertVectorImpl{
        private Object[] elems;
        private int size = 0;
        
        protected ArbreBinariQuasicomplertVectorImpl() {
            this(10); 
        }
        
        protected ArbreBinariQuasicomplertVectorImpl(int max) { 
            elems = (Object[]) new Object[max]; 
        }
        
        protected Object getDada(int pos){
            return elems[pos];
        }

        protected int darrer() {
          return size-1;
        }

        protected int afegirDarrer(Object elem) {
            size++;
            if(size>=elems.length){
                Object[] aux = new Object[2*size];
                System.arraycopy(elems, 0, aux, 0, size);
                //elems = Arrays.copyOf(elems, 2*size);
                elems = aux;
            }
            elems[size-1] = elem;
            
            return size-1;
        }

        protected int esborrarDarrer() {
            size--;
            Object aux=elems[size];
            elems[size] = null;
            return  size;
        }
        
        protected boolean esBuit(){
            return size==0;
        }
        
        protected int getArrel(){
            return 0;
        }

        protected boolean tePare(int pos){
            return pos !=0;
        }        

        protected boolean teFillEsq(int pos){
            return ((pos*2)+1)<size;
        }

        protected boolean teFillDret(int pos){
            return ((pos*2)+2)<size;
        }

        protected int getPare(int pos){
            return (pos-1)/2;
        }
        
        protected int getFillEsq(int pos){
            return (pos*2)+1;
        }

        protected int getFillDret(int pos){
            return (pos*2)+2;
        }
    }

}
